This application claims priority of Korean Patent Application No. 10-2003-0026615 and 10-2004-0018890 filed on Apr. 26, 2003, and Mar. 19, 2004, respectively, in the Korean Intellectual Property Office, the disclosures of which are incorporated herein in their entireties by reference.
1. Field of the Invention
Apparatuses and methods consistent with the present invention relate to a mobile ad hoc network, and more particularly, to an apparatus and method for retransmitting data packets so as to reduce the loss of packets caused in the course of transmission based on a broadcasting method (hereinafter referred to as “broadcast packet”).
2. Description of the Related Art
Mobile ad hoc network refers to a network interconnecting mobile terminals (hereinafter referred to as “nodes”) by use of wireless links, not based on any infrastructure.
Specifically, the mobile ad hoc network is a multihop wireless network without an infrastructure. In the mobile ad hoc network, every link is wireless and every node is mobile. So the mobile ad hoc network can be deployed easily and configured automatically.
However, the nodes constituting the mobile ad hoc network individually and independently move, and for this reason, a decentralization scheme in lieu of a centralization scheme should be employed to control the mobile ad hoc network or to share information among the nodes.
Thus, to control all the nodes constituting a mobile ad hoc network by the use of the decentralization scheme, a mechanism to transmit packets containing control information relative to all the nodes by a broadcasting mechanism is indispensable.
At this time, since the mobile ad hoc network lacks a centralized control device such as an access point of a wireless LAN (local area network) based on the infrastructure therefor, it is highly likely for a packet to be broadcasted simultaneously from more than one node. At this time, if two nodes overlapping with each other in a transmission region, in view of the inherent characteristics of wireless link, send the broadcast packet at the same time, a packet collision between the broadcast packets may occur. Because of the packet collision generated by overlapped paths in broadcast packet transmission, there is a high likelihood that important control information transmitted simultaneously from plural nodes may disappear, thereby lowering the reliability of broadcast packet transmission.
To secure the reliability of the transmission, the mobile ad hoc network system employs a flooding broadcast mechanism.
In the flooding mechanism, a source node initially generating a packet broadcasts the generated packet to all the neighbor nodes, and each of the neighbor nodes, in turn, broadcasts the packet received by it, exactly one time. This process continues until all the reachable nodes in the mobile ad hoc network receive the packet.
FIG. 1 illustrates a flooding mechanism described above. Referring to this figure, the flooding mechanism is described in more detail.
When a sending node broadcasts packets to its neighbor nodes, each of the neighbor nodes broadcasts the broadcast packet received by it to its neighbor nodes. Thus, a node receives the same packet several times, thereby consuming a large portion of the bandwidth and deteriorating the broadcast efficiency.
As illustrated in FIG. 1, a node #3 broadcasts a packet to its neighbor nodes, functioning as a source node and then a node #1 and a node #4 receiving the packet broadcast it to their neighbor nodes within one(1)-hop. At this time, a node #2, a node #6 and a node #7 receive the packet from the node #1 and a node #5 and a node #6 receive the packet from the node #4. Subsequently, the node #2, the node #5, the node #6 and the node #7 broadcast the packets received by them again to their neighbor nodes. At this time, most of the transmission regions overlap, thereby causing a large amount of packet loss.
According to the flooding mechanism, a single node is forced to receive the same packet several times redundantly, and as a result, a single packet loss can be compensated with other redundant packets and the broadcast reliability is not seriously degraded.
By contrast, the flooding mechanism seriously degrades the broadcast efficiency because the redundant packets are forwarded several times with the consumption of bandwidth.
Accordingly, in order to improve the broadcast efficiency in the mobile ad hoc network, a number of research groups have proposed a minimization of the number of the redundant packets.
One of the proposed methods is not to broadcast a packet repeatedly until all the nodes receive the broadcast packet but to allow only a part of neighbor nodes to broadcast the received packet again.
In the mobile ad hoc network, since mobile nodes are connected one to another by a wireless link without an infrastructure therefor, the network topology changes in time due to the mobility of the nodes constituting the network. Thus, the nodes belonging to the mobile ad hoc network periodically exchange with one another hello packets containing their own addresses and information on the neighbor nodes identified, to know the states of the neighbor nodes and the topology of the whole network.
Based on the information on neighbor nodes collected by the hello packet, a broadcast packet sender may select some nodes among the neighbor nodes as relayer nodes. As a typical mechanism, there is an Ad Hoc broadcast protocol (AHBP). The AHBP refers to a protocol under which an arbitrary node having information on the neighbor nodes within 2-hops selects an arbitrary node among the nodes within an 1-hop as a relayer node, and only the selected relayer node can broadcast the packet transmitted by the arbitrary node, again.
FIG. 2 specifically illustrates an operation of the AHBP.
Referring to this figure, some nodes broadcast packets so as to effectively use bandwidth by reducing the number of redundant packets as much as possible.
For example, if a node #3 is a source node, a node #1 and a node #4 are selected as relayer nodes by the node #3 and a node #6 is selected as a relayer node by either the node #1 or the node #4, node #6 broadcasts the packet as a relayer node.
However, minimization of the redundant packets by this method degrades reliability due to single packet loss. In particular, the degradation is worsened when the relayer node loses the packet.
Further, nodes constituting the mobile ad hoc network freely move and are involved in the transmission and reception of data independently from other nodes in the wireless link environment and thus there is a high likelihood that several nodes transmitting a broadcast packet simultaneously as depicted in FIG. 3. If so, the reliability will be greatly lowered because of packet collision generated whenever the paths overlap.
In this connection, there is a need for a mechanism to secure the reliability and the broadcast efficiency by reducing any effect from packet collision generated due to overlapped paths when more than one node transmits a broadcast packet in the mobile ad hoc network environment, and transmitting the broadcast packet efficiently and securely.